package com.lzq.leetcode.lanqiao.tempates;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class ST {

    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] l1 = reader.readLine().split(" ");
        int n = Integer.parseInt(l1[0]);
        int q = Integer.parseInt(l1[1]);

        int[] ele = new int[n];
        for (int i=0; i<n; i++) {
            ele[i] = Integer.parseInt(reader.readLine());
        }

        // 预处理
        int[][] dpMin = new int[n][22];
        int[][] dpMax = new int[n][22];

        for (int i=0; i<n; i++) {
            dpMax[i][0] = ele[i];
            dpMin[i][0] = ele[i];
        }

        int p = (int) (Math.log(n) / Math.log(2));
        for (int k=1; k<=p; k++) {
            for (int s=0; s+(1<<k)<=n; s++) {
                dpMax[s][k] = Math.max(dpMax[s][k-1], dpMax[s+(1<<(k-1))][k-1]);
                dpMin[s][k] = Math.min(dpMin[s][k-1], dpMin[s+(1<<(k-1))][k-1]);
            }
        }
        // 处理查询
        for (int i=0; i<q; i++) {
            String[] line = reader.readLine().split(" ");
            int l = Integer.parseInt(line[0]) - 1;
            int r = Integer.parseInt(line[1]) - 1;
            int k = (int)(Math.log(r-l+1) / Math.log(2));
            int p1 = l;
            int p2 = r - (1 << k) + 1;
            int max = Math.max(dpMax[p1][k], dpMax[p2][k]);
            int min = Math.min(dpMin[p1][k], dpMin[p2][k]);
            System.out.println(max - min);
        }
    }
}
